/**
 * 
 */
package edu.hitsz.cs.nlp.struct;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

import edu.hitsz.cs.nlp.struct.CfgTree;
import edu.hitsz.cs.nlp.struct.Conll09File;
import edu.hitsz.cs.nlp.struct.Conll09Sentence;


/**
 * @author tm
 *
 */
public class CfgTree implements Cloneable{
	
	public String label;
	public int start;
	public int end;
	public int seq=0;
	public int head=0;
	public int tempseq=0;
	public static String headAdd="+P";
	public String head2tail;
	ArrayList<CfgTree> sonTree;
	
	public CfgTree(){
		sonTree=new ArrayList<CfgTree>();
	}
	
	/**
	 * ��Conll09Sentenceת��ΪTree�ṹ�������non-terminal��ʶ(����non-terminal����POS��ʶ)
	 * @param sen Ҫ��ȡ�ľ���
	 * @param length ���ӳ���
	 * @param signal ͷ�ڵ�λ��
	 * @return
	 */
	public CfgTree depToFlatTree(Conll09Sentence sen, int length, int signal){		
		CfgTree tree=new CfgTree();
		int sin=0;
		CfgTree son=new CfgTree();	
		for(int i=0;i<length;i++)
			if(sen.isFather(signal,i))
				sin=1;
		if(sin==1){
			tree.label=sen.pos[signal]+headAdd;//+headAdd;
			tree.seq=signal+1;
			if(signal==0)
				tree.head=0;
			if(signal>0)
				for(int i=0;i<signal;i++)
					if(sen.head[i].equals(Integer.toString(signal+1))){
						son=depToFlatTree(sen,length,i);
						son.head=tree.seq;
						tree.sonTree.add(son);
					}
			son=depToUnaryTree(sen,length,signal);
			son.head=tree.seq;
			tree.sonTree.add(son);
			if(signal<length-1)
				for(int j=signal+1;j<length;j++)
					if(sen.head[j].equals(Integer.toString(signal+1))){
						son=depToFlatTree(sen,length,j);
						son.head=tree.seq;
						tree.sonTree.add(son);
					}
			return tree;
		}
		else{
			son=depToUnaryTree(sen,length,signal);	
			son.head=tree.seq;
			return son;
		}
	}
	
	/**
	 * ������ṹת��Ϊ�����������ڱ���depToFlatTree()����
	 * @param sen
	 * @param length
	 * @param signal
	 * @return
	 */
	private CfgTree depToUnaryTree(Conll09Sentence sen, int length, int signal){
		CfgTree tree=new CfgTree();
		tree.label=sen.pos[signal];
		tree.seq=signal+1;
		CfgTree son=new CfgTree();
		son.label=sen.form[signal];
		son.seq=signal+1;
		tree.sonTree.add(son);
		return tree;
	}

	/**
	 * ��һ���ַ����ж�ȡ�����ṹ����((S (A x) (C x)))
	 * @param line
	 * @return
	 */
	public CfgTree loadCTree(String line){
		String tempString;
		int len=line.length();
		//tempString=line.substring(1,len-1);
		tempString=line.substring(0,len);
		return loadCTreeIte(tempString,len-2,0);
	}	

	/**
	 * �ݹ�һ���ַ����ж�ȡ�����ṹ������loadCTree����
	 * @param line
	 * @param length
	 * @param i
	 * @return
	 */
	private CfgTree loadCTreeIte(String line,int length,int i){		
		int j;
		while(i<length-1&&line.charAt(i)==' ')
			i++;
		if(i<length-1&&line.charAt(i)=='('){
			CfgTree tree=new CfgTree();
			tree.start=i++;
			j=i;
			while(j<length-1&&line.charAt(j)!=' '){
				j++;
			}
			tree.label=line.substring(i,j);
			assert line.charAt(j)==' ';
			i=j+1;
			while(i<length-1&&line.charAt(i)!=')'){
				CfgTree son=new CfgTree();
				son=loadCTreeIte(line,length,i);
				assert son!=null;
				tree.sonTree.add(son);
				i=son.end;
				i++;
			}
			tree.end=i;
			assert line.charAt(i)==')';
			return tree;
		}
		else if(i<length-1){
			CfgTree terminTree=new CfgTree();
			j=i;
			terminTree.start=j;
			while(j<length-1&&line.charAt(j)!=' '&&line.charAt(j)!=')'){
				j++;
			}
			terminTree.seq=tempseq;
			tempseq++;
			terminTree.end=j-1;
			terminTree.label=line.substring(i,j);
			assert line.charAt(j)==')';
			return terminTree;
		}		
		return null;
	}
	
	/**
	 * ������ṹ�е�seq��head����
	 * @param newSen ��Ҫ�ҵ�ͷ�ڵ��Conll09Sentence
	 * @param newMap ��δ�ҵ�java�汾��maximum entropy,���Բ���Map������������Ȩֵ
	 */
	//��һ�����ṹ�м���ÿ���ʵ����к�ͷ�ڵ�
	public void compCTreeSeqAndHead(Conll09Sentence newSen,HashMap newMap)
	{
		compCTreeSeq(newSen,newMap);
		compCTreeHead(newSen,newMap);
		compCTreeHeads(newSen,newMap);
	}	

	//�������ṹ��Seqֵ
	private void compCTreeSeq(Conll09Sentence newSen,HashMap newMap){
		int n=sonTree.size();
		if(n>0)
			if(n==1)
				seq=sonTree.get(0).seq;
			else{
				for(int i=n-1;i>=0;i--)
					sonTree.get(i).compCTreeSeq(newSen,newMap);
				seq=sonTree.get(whichSon(newSen,newMap)).seq;
			}	
	}
	
	/**
	 * ���POS��ϵ����ͬ�����������ֵѡ���ҵ�ͷ�ڵ���ӽڵ㣬�״�ʹ�õ����������
	 * @param newSen
	 * @param newMap
	 * @return
	 */
	private int whichSon(Conll09Sentence newSen,HashMap newMap){
		int n=sonTree.size();
		String tempString;
		int signal=0;
		int sonposit=0;
		double value=0;
		double tempValue=0;
		for(int i=n-1;i>=0;i--)
		{	
			if(sonTree.get(i).label.equals(label)||
				((label.length()-headAdd.length())>0&&
				sonTree.get(i).label.equals(label.substring(0,label.length()-headAdd.length())))){
				signal=1;
				tempString=newSen.statHeadForMaxentS(i);
				if(newMap.get(tempString)!=null){
					tempValue=Double.parseDouble(newMap.get(tempString).toString());
				}
				if(tempValue>value){
					sonposit=i;
					value=tempValue;
				}
			}				
		}	
		if(signal==0)
			for(int i=n-1;i>=0;i--)
			{	
				tempString=newSen.statHeadForMaxentS(i);
				if(newMap.get(tempString)!=null){
					tempValue=Double.parseDouble(newMap.get(tempString).toString());
				}
				if(tempValue>value){
					sonposit=i;
					value=tempValue;
				}			
			}				
		
		return sonposit;
	}
	
	/**
	 * �ҵ�ͷ�ڵ���ӽڵ㣬��ε������
	 * @return
	 */
	private int whichSon(){
		int n=sonTree.size();
		for(int i=n-1;i>=0;i--)
			if(sonTree.get(i).seq==seq){
				return i;
			}
		return n-1;
	}
	
	/**
	 * �������ṹ��ͷ�ڵ��Headֵ
	 * @param newSen
	 * @param newMap
	 */
	private void compCTreeHead(Conll09Sentence newSen,HashMap newMap){
		int n=sonTree.size();
		if(n==1){
			head=0;
			sonTree.get(0).head=0;
		}
		else if(n>1){
			int i=whichSon();
			sonTree.get(i).compCTreeHead(newSen,newMap);
			head=sonTree.get(i).head;
		}
	}
	
	/**
	 * �������ṹ��Headֵ
	 * @param newSen
	 * @param newMap
	 */
	private void compCTreeHeads(Conll09Sentence newSen,HashMap newMap){
		int n=sonTree.size();
		if(n==1){
			sonTree.get(0).head=head;
			newSen.head[seq]=Integer.toString(head);
			newSen.phead[seq]=Integer.toString(head);
			newSen.deprel[seq]="ROOT";
			newSen.pdeprel[seq]="ROOT";
			//sen.head[seq]=Integer.toString(head);
		}
		else if (n>1){
			int tmp=whichSon();
			for(int i=n-1;i>=0;i--){
				if(i==tmp)
					sonTree.get(i).head=head;
				else
					sonTree.get(i).head=seq+1;
				sonTree.get(i).compCTreeHeads(newSen,newMap);
			}
		}			
	}
	
	/**
	 * �����ṹΪPTB�ṹ���洢���ļ�
	 * @param newWriter
	 * @throws IOException
	 */
	public void storeCTree(FileWriter newWriter) throws IOException{
		newWriter.write("(S");
		storeCTreeIte(newWriter);
		newWriter.write(")");
	}
	
	/**
	 * ��������ṹΪPTB�ṹ���洢���ļ�������storeCTree����
	 * @param newWriter
	 * @throws IOException
	 */
	private void storeCTreeIte(FileWriter newWriter) throws IOException{
		if(sonTree.size()!=0){
			newWriter.write(" ("+label);
			if(sonTree!=null)
				for(int i=0;i<sonTree.size();i++){
					sonTree.get(i).storeCTreeIte(newWriter);
				}
			newWriter.write(")");	
		}
		else
			newWriter.write(" "+label);			
	}

	/**
	 * ��¼��������β��·��
	 * 
	 */
	public void compHead2Tail(){
		String tempstring=label+"-"+start+"-"+end;
		System.out.println(tempstring);
		head2tail=tempstring;
		if(sonTree.size()!=0){
			for(int i=0;i<sonTree.size();i++){
				String sonstring=sonTree.get(i).label+"_____"+sonTree.get(i).start+"_____"+sonTree.get(i).end;
				sonTree.get(i).head2tail=sonstring+"+++++"+head2tail;
				sonTree.get(i).compHead2TailIter();
			}
		}
	}
	public void compHead2TailIter(){
		if(sonTree.size()!=0){
			for(int i=0;i<sonTree.size();i++){
				String tempstring=sonTree.get(i).label+"_____"+sonTree.get(i).start+"_____"+sonTree.get(i).end;
				sonTree.get(i).head2tail=tempstring+"+++++"+head2tail;
				sonTree.get(i).compHead2TailIter();
			}
		}
	}
			
	
	
	/**
	 * ��ʾ��ṹ���նˣ���Ľ�
	 * 
	 */
	public void outputCTree(){
		System.out.print("(");
		outputCTreeIte();
		System.out.print(")\n");
	}	
	private void outputCTreeIte(){
		if(sonTree.size()!=0){
			System.out.print("("+label);
			System.out.print("-"+start);
			System.out.print("-"+end);
			System.out.print("-"+seq);
			System.out.print("-"+head);
			System.out.print("-"+head2tail);
			for(int i=0;i<sonTree.size();i++){
				System.out.print(" ");
				sonTree.get(i).outputCTreeIte();
			}
			System.out.print(")");
		}
		else{
			System.out.print(label);
			System.out.print("-"+start);
			System.out.print("-"+end);
			System.out.print("-"+seq);
			System.out.print("-"+head);
			System.out.print("-"+head2tail);
		}
	}
			
	/**
	 * ��֤����ṹת���ɵ���ṹ����ȷ�ԣ����䷨����ӦΪPOS������POS+headAdd
	 * @return
	 */
	public boolean validateCTree()
	{
		int n=sonTree.size();
		if(n>1)
		{
			for(int i=0;i<n;i++)
				if(!sonTree.get(i).validateCTree())
					return false;
			int len=label.length();
			if(!label.substring(len-headAdd.length(),len).equals(headAdd))
				return false;
		}
		return true;
	}
	
	
	/*
	public Object clone(){
		CfgTree o=null;
		try{
			o = (CfgTree)super.clone();
			if(o.sonTree!=null){
				for(int i=0;i<o.sonTree.size();i++)
					o.sonTree.add(this.sonTree.get(i));
			}
		}
		catch(CloneNotSupportedException e){
			e.printStackTrace();
			}
		return o;
		}
	*/
	
	/**
	 * ����,���Ժ���
	 * ���ļ��е����ַ��������tree�ṹ���洢���ļ���
	 * test1("E:\\codespace\\workspace\\laparser\\","testInCTree.txt","testOutCTree.txt");
	 */
	static public void OpenStoreCTree(String outPath, String inName, String outName){

		String tempString;
		try{
			String inFileName=outPath+inName;
			BufferedReader newReader=new BufferedReader(new FileReader(new File(inFileName)));
			String outFileName=outPath+outName;
			FileWriter newWriter=new FileWriter(outFileName);
			while((tempString=newReader.readLine())!=null){
				CfgTree newTree=new CfgTree();
				newTree=newTree.loadCTree(tempString);					
				newTree.storeCTree(newWriter);
				newWriter.write("\n");
			}
			newReader.close();
			newWriter.close();			
			System.out.println("store CTree file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}		
	}
	
	/**
	*/
	static public void processCTree(String outPath, String inName, String outName){

		String tempString;
		try{
			String inFileName=outPath+inName;
			BufferedReader newReader=new BufferedReader(new FileReader(new File(inFileName)));
			String outFileName=outPath+outName;
			FileWriter newWriter=new FileWriter(outFileName);
			int count=0;
			while((tempString=newReader.readLine())!=null){
				CfgTree newTree=new CfgTree();
				newTree=newTree.loadCTree(tempString);	
				newTree.compHead2Tail();
				//newTree.outputCTree();
				newTree.storeCTree(newWriter);
				newWriter.write("\n");
				System.out.println(count++);
			}
			newReader.close();
			newWriter.close();			
			System.out.println("store CTree file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}		
	}
	
	
	/**
	 * ����,���Ժ���
	 * ��dependency�ļ�ת����PTB�ļ�
	 * Dep2CTree("F:\\codespace\\workspace\\laparser\\",
	 * "preprocess-CoNLL2009-ST-English-train.txt",
	 * "treep-preprocess-CoNLL2009-ST-English-train.txt");
	 * @param outPath
	 * @param inName
	 * @param outName
	 */
	static public void Dep2CTree(String outPath,String inName,String outName){
		Conll09File trainFile=new Conll09File();
		trainFile.readTrainFile(outPath, inName, 0);
		//testFile.preProcessTestFile(path,devName,devNameP,0);
		//trainFile.outputTrainFile();
		CfgTree newTree=new CfgTree();
		int signal=0;		
		try{
			String outFileName=outPath+outName;
			FileWriter newWriter=new FileWriter(outFileName);
			for(int i=0;i<trainFile.totalSentence.size();i++){
				signal=0;
				for(int j=0;j<trainFile.totalSentence.get(i).sentenceLength;j++)
					if(trainFile.totalSentence.get(i).head[j].equals("0")){
						signal=j;
						break;
					};	
				if(i%1000==0)
					System.out.println("Store "+i+"th Ctrees.");
				newTree=newTree.depToFlatTree(trainFile.totalSentence.get(i),
						trainFile.totalSentence.get(i).sentenceLength,signal);
				//newTree.displayCTree();
				newTree.storeCTree(newWriter);
				newWriter.write("\n");
			}
			newWriter.close();			
			System.out.println("store CTree file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}		
	}

	
	/**
	 * ��ȡԭʼ�����ļ��Ͷ�Ӧ�����ṹ�������ṹ��Ӧ�������ϵ
	 * cTreeToDep("F:\\codespace\\workspace\\laparser\\",
	 * 				"preprocess-CoNLL2009-ST-English-development.txt",
	 * 				"tree-preprocess-CoNLL2009-ST-English-development.txt",
	 * 				"simple-nohead-num-CoNLL2009-ST-Chinese-Joint.txt",
	 * 				"out-head-num-CoNLL2009-ST-Chinese-Joint.txt")
	 * @param outPath
	 * @param inName
	 * @param inCTreeName
	 * @param inMapName
	 * @param outName
	 */
	static public void cTreeToDep(String outPath,String inName,String inCTreeName,String inMapName,String outName){
		//����ԭʼ�����ļ�
		Conll09File testFile=new Conll09File();
		testFile.readTestFile(outPath, inName, 0);		
		String tempString;
		//�����Ӧ�����ṹ
		ArrayList<CfgTree> newList=new ArrayList<CfgTree>();
		try{
			String inFileName=outPath+inCTreeName;
			BufferedReader newReader=new BufferedReader(new FileReader(new File(inFileName)));
			while((tempString=newReader.readLine())!=null){
				CfgTree newTree=new CfgTree();
				newTree=newTree.loadCTree(tempString);			
				newList.add(newTree);
			}
			newReader.close();
			System.out.println("load CTree file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}	
		System.out.println(testFile.sentenceNumber);
		System.out.println(newList.size());
		//����ͷ����map
		HashMap<String, Double> feaMap=new HashMap<String, Double>();
		try{
			String inFileName=outPath+inMapName;
			BufferedReader newReader=new BufferedReader(new FileReader(new File(inFileName)));
			while((tempString=newReader.readLine())!=null){
				String[] words=tempString.split("\t");
				String word=words[0];
				double wordFreq=Double.parseDouble(words[1]);
				feaMap.put(word,wordFreq);
			}
			newReader.close();
			System.out.println("load CTreeFeaMap file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}
		System.out.println(feaMap.size());
		for(int i=0;i<testFile.sentenceNumber;i++){
			System.out.println(i+"th sentence is processing");
			//testFile.totalSentence.get(i).outputTrainSentence();
			//newList.get(i).outputCTree();
			newList.get(i).compCTreeSeqAndHead(testFile.totalSentence.get(i), feaMap);
		}
		//newList.get(0).outputCTree();
		//testFile.totalSentence.get(0).outputTrainSentence();
		//�洢�ļ�
		try{
			String outFileName=outPath+outName;
			FileWriter newWriter=new FileWriter(outFileName);
			for(int i=0;i<testFile.sentenceNumber;i++){
				testFile.totalSentence.get(i).storeTrainSentence(newWriter);
			}
			newWriter.close();			
			System.out.println("store CTree file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}	
		System.out.println("store processed file all done");
		
	}
	
	/**
	 * ��ȡԭʼ�����ļ���Ȼ��ת��ΪFlat���ļ������洢ͷ�ڵ�ͳ����Ϣ��ͷ�ڵ�������Ϣ
	 * exDepHead("F:\\codespace\\workspace\\laparser\\",
	 * 			"preprocess-CoNLL2009-ST-English-train.txt",
	 * 			"headstat-preprocess-CoNLL2009-ST-English-train.txt",
	 * 			"headfea-preprocess-CoNLL2009-ST-English-train.txt");
	 * @param outPath
	 * @param inDepName
	 * @param outHeadStatName
	 * @param outHeadFeaName
	 */
	static public void exDepHead(String outPath,String inDepName,String outHeadStatName,String outHeadFeaName){
		Conll09File trainFile=new Conll09File();
		trainFile.readTrainFile(outPath, inDepName, 0);
		//testFile.preProcessTestFile(path,devName,devNameP,0);
		//trainFile.outputTrainFile();
		CfgTree newTree=new CfgTree();
		int signal=0;		
		try{
			String headStatName=outPath+outHeadStatName;
			FileWriter headStatWriter=new FileWriter(headStatName);
			String headFeaName=outPath+outHeadFeaName;
			FileWriter headFeaWriter=new FileWriter(headFeaName);
			for(int i=0;i<trainFile.totalSentence.size();i++){
				signal=0;
				for(int j=0;j<trainFile.totalSentence.get(i).sentenceLength;j++)
					if(trainFile.totalSentence.get(i).head[j].equals("0")){
						signal=j;
						break;
					};	
				if(i%1000==0)
					System.out.println("Store "+i+"th Ctrees.");
				newTree=newTree.depToFlatTree(trainFile.totalSentence.get(i),
						trainFile.totalSentence.get(i).sentenceLength,signal);
				newTree.outputCTree();
				
			}
			
			headStatWriter.close();			
			System.out.println("store CTree file done.");
			headFeaWriter.close();			
			System.out.println("store CTree file done.");
		}
		catch(IOException e){
			System.out.println("IOException: " + e);
		}	
	}
	
	public static void main(String[] args){	
		Dep2CTree("F:\\codespace\\workspace\\laparser\\",
				 "preprocess-CoNLL2009-ST-English-Joint-ood.txt","treep-preprocess-CoNLL2009-ST-English-Joint-ood.txt");
	}
}

